package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-100-liked
 * <p>
 * 贪心   动态规划    学习视频：https://www.bilibili.com/video/BV1WK4y1R71x/?spm_id_from=333.788&vd_source=fc4b1ad9e6d85555b8581640913d36a5
 * 参考通过     注意边界
 *
 * @author yulongTian
 * @create 2024-07-15 22:02
 */
public class Test74 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 0};
        System.out.println(new Test74().canJump(nums));
    }

    /*
    参考思路:
    找到当前最大的步数再去跳跃。首先设最大步数n，然后每次只走一格，如果走到的该格步数大于n，
    则替换掉当前的n，反之则n-1；如果n减到0之后则则证明最大的步数都无法移动，故返回false
     */
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            if (nums[0] == 0) {
                return true;
            }
        }
        int max_step = nums[0];
        if (max_step <= 0) {
            return false;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= max_step) {
                max_step = nums[i];
            } else {
                max_step--;
            }
            if (i == nums.length - 1) {
                if (max_step == 0) {
                    return true;
                }
            }
            if (max_step <= 0) {
                return false;
            }
        }
        return true;
    }

    /*
    参考题解
     */
    public boolean canJump_(int[] nums) {
        int n = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= nums.length - i - 1) {
                return true;
            }
            //n代表最大步数，每走一步则减少一步，移动到下一个数进行比较
            //如果该步数比n更大或相等时，则用此步数替换掉n
            if (n > nums[i]) {
                n--;
            } else {
                n = nums[i];
            }
            //当最大步数n为零则证明以及无法移动，返回false
            if (n == 0) {
                return false;
            }
        }
        return true;
    }

}
